home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Caml Light 0.7 / Caml Light 0.7 source / src / yacc / mkpar.c < prev    next >
Text File  |  1995-06-01  |  6KB  |  358 lines
  1.  
  2. #include "defs.h"
  3.  
  4. action **parser;
  5. int SRtotal;
  6. int RRtotal;
  7. short *SRconflicts;
  8. short *RRconflicts;
  9. short *defred;
  10. short *rules_used;
  11. short nunused;
  12. short final_state;
  13.  
  14. static int SRcount;
  15. static int RRcount;
  16.  
  17. extern action *parse_actions();
  18. extern action *get_shifts();
  19. extern action *add_reductions();
  20. extern action *add_reduce();
  21.  
  22.  
  23. make_parser()
  24. {
  25.     register int i;
  26.  
  27.     parser = NEW2(nstates, action *);
  28.     for (i = 0; i < nstates; i++)
  29.     parser[i] = parse_actions(i);
  30.  
  31.     find_final_state();
  32.     remove_conflicts();
  33.     unused_rules();
  34.     if (SRtotal + RRtotal > 0) total_conflicts();
  35.     defreds();
  36. }
  37.  
  38.  
  39. action *
  40. parse_actions(stateno)
  41. register int stateno;
  42. {
  43.     register action *actions;
  44.  
  45.     actions = get_shifts(stateno);
  46.     actions = add_reductions(stateno, actions);
  47.     return (actions);
  48. }
  49.  
  50.  
  51. action *
  52. get_shifts(stateno)
  53. int stateno;
  54. {
  55.     register action *actions, *temp;
  56.     register shifts *sp;
  57.     register short *to_state;
  58.     register int i, k;
  59.     register int symbol;
  60.  
  61.     actions = 0;
  62.     sp = shift_table[stateno];
  63.     if (sp)
  64.     {
  65.     to_state = sp->shift;
  66.     for (i = sp->nshifts - 1; i >= 0; i--)
  67.     {
  68.         k = to_state[i];
  69.         symbol = accessing_symbol[k];
  70.         if (ISTOKEN(symbol))
  71.         {
  72.         temp = NEW(action);
  73.         temp->next = actions;
  74.         temp->symbol = symbol;
  75.         temp->number = k;
  76.         temp->prec = symbol_prec[symbol];
  77.         temp->action_code = SHIFT;
  78.         temp->assoc = symbol_assoc[symbol];
  79.         actions = temp;
  80.         }
  81.     }
  82.     }
  83.     return (actions);
  84. }
  85.  
  86. action *
  87. add_reductions(stateno, actions)
  88. int stateno;
  89. register action *actions;
  90. {
  91.     register int i, j, m, n;
  92.     register int ruleno, tokensetsize;
  93.     register unsigned *rowp;
  94.  
  95.     tokensetsize = WORDSIZE(ntokens);
  96.     m = lookaheads[stateno];
  97.     n = lookaheads[stateno + 1];
  98.     for (i = m; i < n; i++)
  99.     {
  100.     ruleno = LAruleno[i];
  101.     rowp = LA + i * tokensetsize;
  102.     for (j = ntokens - 1; j >= 0; j--)
  103.     {
  104.         if (BIT(rowp, j))
  105.         actions = add_reduce(actions, ruleno, j);
  106.     }
  107.     }
  108.     return (actions);
  109. }
  110.  
  111.  
  112. action *
  113. add_reduce(actions, ruleno, symbol)
  114. register action *actions;
  115. register int ruleno, symbol;
  116. {
  117.     register action *temp, *prev, *next;
  118.  
  119.     prev = 0;
  120.     for (next = actions; next && next->symbol < symbol; next = next->next)
  121.     prev = next;
  122.  
  123.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  124.     {
  125.     prev = next;
  126.     next = next->next;
  127.     }
  128.  
  129.     while (next && next->symbol == symbol &&
  130.         next->action_code == REDUCE && next->number < ruleno)
  131.     {
  132.     prev = next;
  133.     next = next->next;
  134.     }
  135.  
  136.     temp = NEW(action);
  137.     temp->next = next;
  138.     temp->symbol = symbol;
  139.     temp->number = ruleno;
  140.     temp->prec = rprec[ruleno];
  141.     temp->action_code = REDUCE;
  142.     temp->assoc = rassoc[ruleno];
  143.  
  144.     if (prev)
  145.     prev->next = temp;
  146.     else
  147.     actions = temp;
  148.  
  149.     return (actions);
  150. }
  151.  
  152.  
  153. find_final_state()
  154. {
  155.     register int goal, i;
  156.     register short *to_state;
  157.     register shifts *p;
  158.  
  159.     p = shift_table[0];
  160.     to_state = p->shift;
  161.     goal = ritem[1];
  162.     for (i = p->nshifts - 1; i >= 0; --i)
  163.     {
  164.     final_state = to_state[i];
  165.     if (accessing_symbol[final_state] == goal) break;
  166.     }
  167. }
  168.  
  169.  
  170. unused_rules()
  171. {
  172.     register int i;
  173.     register action *p;
  174.  
  175.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  176.     if (rules_used == 0) no_space();
  177.  
  178.     for (i = 0; i < nrules; ++i)
  179.     rules_used[i] = 0;
  180.  
  181.     for (i = 0; i < nstates; ++i)
  182.     {
  183.     for (p = parser[i]; p; p = p->next)
  184.     {
  185.         if (p->action_code == REDUCE && p->suppressed == 0)
  186.         rules_used[p->number] = 1;
  187.     }
  188.     }
  189.  
  190.     nunused = 0;
  191.     for (i = 3; i < nrules; ++i)
  192.     if (!rules_used[i]) ++nunused;
  193.  
  194.     if (nunused)
  195.     if (nunused == 1)
  196.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  197.     else
  198.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  199. }
  200.  
  201.  
  202. remove_conflicts()
  203. {
  204.     register int i;
  205.     register int symbol;
  206.     register action *p, *pref;
  207.  
  208.     SRtotal = 0;
  209.     RRtotal = 0;
  210.     SRconflicts = NEW2(nstates, short);
  211.     RRconflicts = NEW2(nstates, short);
  212.     for (i = 0; i < nstates; i++)
  213.     {
  214.     SRcount = 0;
  215.     RRcount = 0;
  216.     symbol = -1;
  217.     for (p = parser[i]; p; p = p->next)
  218.     {
  219.         if (p->symbol != symbol)
  220.         {
  221.         pref = p;
  222.         symbol = p->symbol;
  223.         }
  224.         else if (i == final_state && symbol == 0)
  225.         {
  226.         SRcount++;
  227.         p->suppressed = 1;
  228.         }
  229.         else if (pref->action_code == SHIFT)
  230.         {
  231.         if (pref->prec > 0 && p->prec > 0)
  232.         {
  233.             if (pref->prec < p->prec)
  234.             {
  235.             pref->suppressed = 2;
  236.             pref = p;
  237.             }
  238.             else if (pref->prec > p->prec)
  239.             {
  240.             p->suppressed = 2;
  241.             }
  242.             else if (pref->assoc == LEFT)
  243.             {
  244.             pref->suppressed = 2;
  245.             pref = p;
  246.             }
  247.             else if (pref->assoc == RIGHT)
  248.             {
  249.             p->suppressed = 2;
  250.             }
  251.             else
  252.             {
  253.             pref->suppressed = 2;
  254.             p->suppressed = 2;
  255.             }
  256.         }
  257.         else
  258.         {
  259.             SRcount++;
  260.             p->suppressed = 1;
  261.         }
  262.         }
  263.         else
  264.         {
  265.         RRcount++;
  266.         p->suppressed = 1;
  267.         }
  268.     }
  269.     SRtotal += SRcount;
  270.     RRtotal += RRcount;
  271.     SRconflicts[i] = SRcount;
  272.     RRconflicts[i] = RRcount;
  273.     }
  274. }
  275.  
  276.  
  277. total_conflicts()
  278. {
  279.     fprintf(stderr, "%s: ", myname);
  280.     if (SRtotal == 1)
  281.     fprintf(stderr, "1 shift/reduce conflict");
  282.     else if (SRtotal > 1)
  283.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  284.  
  285.     if (SRtotal && RRtotal)
  286.     fprintf(stderr, ", ");
  287.  
  288.     if (RRtotal == 1)
  289.     fprintf(stderr, "1 reduce/reduce conflict");
  290.     else if (RRtotal > 1)
  291.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  292.  
  293.     fprintf(stderr, ".\n");
  294. }
  295.  
  296.  
  297. int
  298. sole_reduction(stateno)
  299. int stateno;
  300. {
  301.     register int count, ruleno;
  302.     register action *p;
  303.  
  304.     count = 0;
  305.     ruleno = 0; 
  306.     for (p = parser[stateno]; p; p = p->next)
  307.     {
  308.     if (p->action_code == SHIFT && p->suppressed == 0)
  309.         return (0);
  310.     else if (p->action_code == REDUCE && p->suppressed == 0)
  311.     {
  312.         if (ruleno > 0 && p->number != ruleno)
  313.         return (0);
  314.         if (p->symbol != 1)
  315.         ++count;
  316.         ruleno = p->number;
  317.     }
  318.     }
  319.  
  320.     if (count == 0)
  321.     return (0);
  322.     return (ruleno);
  323. }
  324.  
  325.  
  326. defreds()
  327. {
  328.     register int i;
  329.  
  330.     defred = NEW2(nstates, short);
  331.     for (i = 0; i < nstates; i++)
  332.     defred[i] = sole_reduction(i);
  333. }
  334.  
  335. free_action_row(p)
  336. register action *p;
  337. {
  338.   register action *q;
  339.  
  340.   while (p)
  341.     {
  342.       q = p->next;
  343.       FREE(p);
  344.       p = q;
  345.     }
  346. }
  347.  
  348. free_parser()
  349. {
  350.   register int i;
  351.  
  352.   for (i = 0; i < nstates; i++)
  353.     free_action_row(parser[i]);
  354.  
  355.   FREE(parser);
  356. }
  357.  
  358.